home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1996 #15 / Monster Media Number 15 (Monster Media)(July 1996).ISO / prog_c / cuj0696.zip / DWYER.ZIP / FREQ.TST / README.FRQ < prev    next >
Text File  |  1995-12-29  |  8KB  |  250 lines
  1.  
  2. DESCRIPTION OF THE FREQUENCY TEST
  3.  
  4. Introduction
  5. ------------
  6.  
  7. Of the tests described in this article, the frequency test,
  8. also called the equidistribution test by Knuth [K1, p. 59],
  9. is the easiest to understand.  What you do is grind out a
  10. few hundred variates and check the see how uniformly they
  11. are distributed.  That isn't meant to imply that the variates
  12. should occur with the same frequency because that wouldn't be
  13. random behavior.
  14.  
  15. The frequency test is implemented as program freqtst.  This
  16. program provides two tests - a Kolmogorov-Smirnov (KS) test
  17. and a chi-square test.  Program freqtst gets its user-inputs
  18. interactively - that is, from stdin.  Alternatively, stdin
  19. can be redirected to a file.  Outputs are written to both
  20. stderr and stdout - program prompts and error messages go
  21. the stderr, results are written to stdout.  The output to
  22. stdout can be redirected to a file.
  23.  
  24. Running the Frequency Test
  25. --------------------------
  26.  
  27. To start program freqtst, you can say simply
  28.  
  29.     freqtst
  30.  
  31. and you will be prompted for the required inputs.
  32.  
  33. Alternatively, you can say
  34.  
  35.     freqtst < [myfile.inp]
  36.  
  37. and the program will take its input data from myfile.inp.
  38.  
  39. The first two input parameters are:
  40.  
  41.     o Seed for the random number generator (-1 = Time of day)
  42.     o Designation of generator to be tested
  43.  
  44. The third parameter specifies the test to be performed:
  45.  
  46.     o C = Chi-square
  47.     o K = Kolmogorov-Smirnov
  48.  
  49. Remaining inputs depend on the choice of test. They are
  50. described in the following sections.  The KS test is
  51. described first because techniques used there are
  52. used in the chi-square test, too.
  53.  
  54.  
  55. Kolmogorov-Smirnov Frequency Test
  56. =================================
  57.  
  58. Purpose of Test  (J.D.)
  59. -----------------------
  60.  
  61. Other than to prove that the generator under
  62. test is random, there must be some higher one
  63. although I am unable at the moment to cobble
  64. one up.
  65.  
  66.  
  67. Description of Program Flow
  68. ---------------------------
  69.  
  70. There are two stages to the KS test sequence.  In the first stage,
  71. uniform variates are gathered, sorted and analyzed by a KS procedure
  72. to yield two arrays of probabilities, P+ and P-. In the second stage,
  73. these arrays are sorted and subjected to another KS procedure.
  74.  
  75. Outputs are two statistics, final Kn+ and Kn-, and corresponding
  76. percentage points from the KS distribution function.
  77.  
  78. Invocation of Test
  79. ------------------
  80.  
  81. Start the program as described above.  Your first two inputs
  82. are seed and choice of generator.  The third input must be "K"
  83. to get you into the KS test procedure.
  84.  
  85. If you have your data stored in a file, you can redirect
  86. the input unit to the file with
  87.  
  88.     freqtst < [myfile.inp]
  89.  
  90. This file will look like this:
  91.  
  92. 37417    # Starting Seed (-1 = time of day)
  93. X    # Generator Desired (X = Run-Time Lib rand)
  94. K    # Type of Test (K = Kolmogorov-Smirnov)
  95. 1024    # Number of Samples per Run
  96. 100    # Number Runs for K-S on K-S Test
  97.  
  98. Program Prompts and User Responses
  99. ----------------------------------
  100.  
  101. Program prompts (written to stderr) and result printouts
  102. (written to stdout) will appear on your screen.  Figure.1f
  103. shows what freqtst writes to your screen. The data in the
  104. figure.occurs when you redirect the input unit to a file
  105. with the data shown above.
  106.  
  107. There are 41 lines in this printout with results mixed in
  108. with command prompts. Picking out results can be a chore.
  109. If you prefer to redirect the results written to stdout to
  110. a disk file, you say:
  111.  
  112.     freqtst < [myfile.inp] > [myfile.out]
  113.  
  114. Figure.2f shows what you'll see on your CRT and figure.3f
  115. shows what you'll find in myfile.out.
  116.  
  117.  
  118. Description of Algorithm
  119. ------------------------
  120.  
  121. The KS algorithm implemented in program freqtst is executed
  122. in two source modules, ksfreq.c and execkosm.c:
  123.  
  124. 1.  ksfreq.c - Function KSFreq is called N times in
  125.     execkosm.c to produce N sets of KS statistics and
  126.     probabilities.  N is the number of KS runs specified
  127.     by the user.  Each set consists of four numbers - two
  128.     statistics K+ and K- and two probabilities P+ and P-.
  129.     The steps executed in this module, similar to those
  130.     given in [K1, pp. 48-49], are:
  131.  
  132.     Step 1.  Gather M uniform variates from the generator
  133.              specified by the user.  Each variate is a 15-bit
  134.          integer. The number (M) of variates generated is
  135.          specified by the user as 'Samples per K-S Run' as
  136.          shown previously.
  137.  
  138.     Step 2.  Sort the M-array of variates in ascending order.
  139.  
  140.     Step 3.  Calculate K+ and K- as follows:
  141.  
  142.          Let V[j] be the sorted array of uniform variates.
  143.          Then
  144.  
  145.             K+ = max(j/M - V[j]/MAX_SAMPS),     j=1,M
  146.             K- = max(V[j]/MAX_SAMPS - (j-1)/M), j=1,M
  147.  
  148.          where MAX_SAMPS = 1 + MAX_RAND = 32768.
  149.  
  150.          Calculations are performed in floating point type
  151.          double.
  152.  
  153.          Function KSmirnov() is called to produce corresponding
  154.          probabilities:
  155.  
  156.         P+ = KSmirnov(M, Kn+)
  157.         P- = KSmirnov(M, Kn-)
  158.  
  159.          Because random deviates are stored as integers, function
  160.          KSCalc(), which processes an array of type double, is not
  161.          used.
  162.  
  163.     Step 4.  Output K+, P+, K-, P-
  164.  
  165.  
  166. 2.  execkosm.c - This module applies the KS-on-KS portion of
  167.     this algorithm.
  168.  
  169.     Step 1.  Call function KSFreq() to produce KS probabilities.
  170.          This function implements the KS algorithm described
  171.          previously.  These probabilities are stored in two
  172.          arrays.  One is called PosProbAry; it holds the P+
  173.          probabilities.  The other array is called NegProbAry;
  174.          it holds the P- probabilities.  The number of times
  175.          that KSFreq is called to produce KS pairs is specified
  176.              by user as "K-S Runs For KS-on-KS Calculation."
  177.  
  178.     Step 2.  Sort each array in ascending order.
  179.  
  180.     Step 3.  Call function KSCalc() to calculate statistics
  181.          and probabilities for each array:
  182.  
  183.          Let M be the number of pairs produced at Step 1.
  184.  
  185.        o Get statistics and probabilities for P+:
  186.          KSCalc(PosProbAry, M, &KnPlusStat, &KnPlusProb,
  187.         &KnMinusStat, &KnMinusProb)
  188.  
  189.          Print statistics and probabilities.
  190.  
  191.        o Get statistics and probabilities for P-:
  192.          KSCalc(NegProbAry, M, &KnPlusStat, &KnPlusProb,
  193.         &KnMinusStat, &KnMinusProb)
  194.  
  195.          Print statistics and probabilities.
  196.  
  197.  
  198. Timing Estimates
  199. ----------------
  200.  
  201. The run described above required about 6.6 seconds on my
  202. Pentium 100.  Naturally, the time required depends on the
  203. generator.  For the data shown above, the range of times is
  204. from 6.6 seconds for the MSC library function rand() to 7.3
  205. seconds for the generator by Stephen L. Moshier.
  206.  
  207.  
  208.  
  209. Chi-Square Frequency Test
  210. =========================
  211.  
  212.  
  213. Description of Program Flow
  214. ---------------------------
  215.  
  216. There are two stages to the chi-square frequency test.
  217. The first stage is devoted to generating and tallying
  218. variates and calculating 100 chi-square probabilities.
  219. The second stage consists of subjecting the resulting
  220. array of probabilities to Kolmogorov-Smirnov analysis.
  221.  
  222. Output consists of Kolmogorov-Smirnov statistics and
  223. probabilities as described previously.
  224.  
  225. Figure.4f shows a sample input file, figure.5f shows the
  226. prompts and responses written to stderr and figure.6f
  227. shows the results written to stdout.
  228.  
  229. The chi-square test procedure is implemented in two
  230. modules, exchisq.c and chisqfrq.c.  In the first stage,
  231. module exchisq.c gets program control data, calculates
  232. 100 chi-square probabilities by calling ChiSqFreq() to
  233. get statistics and function chdtr() to get probabilities.
  234.  
  235. In the second stage, function KSCalc() is called to
  236. analyze the array of probabilities.  This function
  237. returns Kolmogorov statistics Kn+ and Kn- and their
  238. corresponding probabilities P+ and P-.  These data
  239. are then printed.
  240.  
  241.  
  242. Timing Estimates
  243. ----------------
  244.  
  245. The run shown in figure.4f required about 2.0 seconds on my
  246. Pentium 100.  Naturally, the time required depends on the
  247. generator (and the CPU).  For the data shown above, the range
  248. of times is from 2.0 seconds for the MSC library function rand()
  249. to 9.0 seconds for the generator by Stephen L. Moshier.
  250.